The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
The Internet is built around a large variety of transmission and switching systems and the information transfer is aggregated into packets, which are individually forwarded and switched toward their destinations. The main tasks of a router or switch are to receive a packet from the input port, find its destination port with regard to the routing table, transfer the packet to the output port via the switch fabric and finally transmit it on the output line. If a burst of packets destined to the same output port arrives, all packets cannot be transmitted on the fly and thus some of them need to be buffered. A critical aspect of the switch architecture is the placement of buffers.
In the Input Queuing (IQ) switch architecture packets arriving from the input lines are queued at the input ports. The packets are then extracted from the input queues to cross the switch fabric and to be forwarded to the output ports. The IQ architecture is used extensively in the design of high-speed routers. An optical switch operates on fixed-size cells and the time that elapses between two consecutive switching decisions is called a time slot. Each arriving packet is divided into cells at the input, and these cells are scheduled across the switch fabric separately. When the last cell arrives, the packet is reassembled and sent on the output link.
A major issue in the design of IQ switches is the scheduler that controls the access to the switching fabric in order to avoid contention at the input and the output ports. Every time slot, the scheduler determines the configuration of the switch, that is a matching between the inputs and the outputs, and each input queue is allowed to forward a cell to the output port it is matched to, if any.
Underlying the design of a wide range of switch architectures is the assumption that the switch configuration time is negligible compared to the cell transmission time. However, in optical switches the configuration time dominates over the cell transmission time.
In an optical switching fabric, input data modulates a tunable-wavelength laser that is directed toward a plurality of tuned-wavelength receivers. Switching one of a plurality of inputs to reach one of a plurality of outputs is achieved by tuning the lasers to one of a plurality of different wavelengths that matches a desired receiver. However, tuning any of the lasers requires a non-zero amount of time. In such a switch, reconfiguring the switching fabric makes it unavailable for a number of time slots equal to the configuration delay. Minimizing the effects of reconfiguration overhead on the switch performance requires specially designed schedulers that hold each configuration for several time slots, thus reducing the number of reconfigurations.
Therefore, in an Input-Queued (IQ) architecture, data packets are held in input queues while the lasers are tuned, then released to the lasers for transmission. Packets in the input queues are divided into cells of unit length. Each cell requires switching to one and only one output port associated with one receiver. When multiple cells need to be switched to the same output port, a first cell may be switched to the receiver associated with the output port, but transmitting one or more of the other cells is pre-empted until the first cell is transmitted and the receiver becomes available.
To achieve maximum efficiency, the scheduler must find a laser tuning arrangement that allows transmitting as many cells as possible to receivers and that minimizes the number of cells that must wait. The problem is complicated since in optical switches so-called configuration delay, which is the time required to reconfigure the switching fabric, is non-negligible with respect to the cell transmission time. In general, a scheduler selects a new matching of lasers to receivers, a non-zero configuration delay C occurs as the lasers are tuned, and the configuration is held for a pre-determined period of time as cells are transferred to the receivers.
Selecting which cells to transmit, using which laser and frequency, is performed by a scheduler in the optical switch. An arbitration sub-task performed by the scheduler, in which a cell at an input queue is selected for an available receiver associated with the correct output port, may be viewed as a bipartite matching. In bipartite scheduling, given a set of packets in the input queues, the makespan of the schedule is determined by a sum of the total configuration holding time and the configuration overhead C. Restated, a goal of efficient optical switch operation is to find a schedule of minimum makespan that forwards all packets to the output ports.
In pre-emptive scheduling, cells from one queue can be scheduled in different configurations, but scheduling complexity depends to an extent on the number of packets in the input queues. In non-preemptive bipartite scheduling, all cells from a single queue are scheduled in just one configuration; therefore, all cells in the queue can be transmitted serially using that configuration until the queue is empty.
A non-preemptive bipartite scheduler has a number of advantages over pre-emptive scheduling approaches. First, the complexity of the scheduler does not depend on the number of packets in the input queues, but only on switch size. The number of re-configurations of the switching fabric is minimized. High-speed operation is possible, and the scheduler can efficiently handle variable-size packets without maintaining packet reassembly buffers.
While non-preemptive bipartite scheduling is theoretically superior for the reasons just given, prior approaches have not adequately solved the Non-Preemptive Bipartite Scheduling (NPBS) problem. Relevant literature in the field, which is further discussed in the provisional application from which priority is claimed herein, includes:
N. McKeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Transactions on Networking, vol. 7, no. 2, pp. 188-201, April 1999. The Non-Preemptive Bipartite Scheduling (NPBS) problem was studied in the context of matrix decomposition for zero configuration delay.
C. C. Ribeiro, M. Minoux and M. C. Penna, “An Optimal Column-Generation-with-Ranking Algorithm for Very Large Scale Set Partitioning Problems in Traffic Assignment,” European Journal of Operational Research, Vol. 41, pp. 232-239, 1989, proposes solving the NPBS problem optimally using a branch and bound procedure.
M. Prais and C. C. Ribeiro, “Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment,” INFORMS Journal on Computing, Vol. 12, pp. 164-176, 2000, propose a heuristic called Reactive Greedy Randomized Adaptive Search Procedure (GRASP).
V. Vokkarane et al., “Segmentation-Based Non-Preemptive Scheduling Algorithms for Optical Burst-Switched Networks,” an online publication available at the time of this writing in the file WOBS03_Sch.pdf of the folder /˜jjue/publications/ of the domain utdallas.edu on the World Wide Web, states that data channel scheduling in OBS networks is the process of assigning an outgoing data channel for the unscheduled arriving burst. Data channel scheduling in OBS networks is different from traditional IP scheduling. In IP, each core node stores the packets in electronic buffers and schedules them on the desired output port. In OBS, once a burst arrives at a node, it must be sent to the next node without storing the burst in electronic buffers. The authors assume that each OBS node supports full-optical wavelength conversion.
Preemptive batch scheduling is considered in Shlomi Dolev and Alexander Kesselman, “Bounded Latency Scheduling Scheme for ATM Cells,” Proceedings of The 4th IEEE Symposium on Computers and Communications (ISCC'99), pp. 273-277.
F. Afrati, T. Aslanidis, E. Bampis, and I. Milis, “Scheduling in Switching Networks with Set-up Delays,” ALGOTEL'2002, Muze, France, May 2002.
M. S. Borella and B. Mukherjee, “Efficient Scheduling of Nonuniform Packet Traffic in a WDM/TDM Local Ligthwave Network with Arbitrary Transceiver Tuning Latencies,” IEEE J. on Selected Areas on Communication, Vol. 14, pp. 923-934, June 1996.
G. Bongiovanni, D. Coppersmith, and C. K. Wong, “An Optimal Time Slot Assignment for a SS/TDMA System with Variable Number of Transponders,” IEEE Transactions on Communication, Vol. 29, pp. 721-726, 1981.
S. Chalasani and A. Varma, “Efficient Time-slot Assignment Algorithms for SS/TDMA Systems with Variable Bandwidth Beams,” IEEE Trans. Commun., Vol. 42, no. 3, pp. 1359-1370, March 1994.
M. Chen and T. S. Yum, “A Conflict-free Protocol for Optical WDMA Networks,” in Proc. GLOBECOM'91, pp. 1276-1281, 1991.
P. Crescenzi, X. Deng, C. Papadimitriou, “On Approximating a Scheduling Problem,” Journal of Combinatorial Optimization, Vol. 5, pp. 287-297, 2001.
S. Dolev and A. Kesselman, “Bounded Latency Scheduling Scheme for ATM Cells,” Journal of Computer Networks, Vol. 32(3), pp 325-331, March 2000.
S. Even, A. Itai, and A. Shamir, “On the complexity of timetable and multicommodity ow problems,” SIAM J. Computing, Vol. 5, pp. 691-703, 1976.
A. Ganz and Y. Gao, “A Time-wavelength Assignment Algorithm for a WDM Star Network,” in Proc. INFOCOM'92, pp. 2144-2150, 1992.
M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP Completeness,” W. H. Freeman, San Francisco, 1979.
T. Gonzalez and S. Sahni, “Open Shop Scheduling to Minimize Finish Time,” Journal of the ACM, Vol. 23, pp. 665-679, 1976.
S. Gopal and C. K. Wong, “Minimizing the Number of Switchings in a SS/TDMA System,” IEEE Trans. Commun., Vol. COM-33, pp. 497-501, June 1985.
T. Inukai, “An Efficient SS/TDMA Time Slot Assignment Algorithm,” IEEE Transactions on Communication, Vol. 27, pp. 1449-1455, 1979.
R. Jain, K. Somalwar, J. Werth, and J. C. Browne, “Scheduling Parallel I/O Operations in Multiple-Bus Systems,” J. Parallel and Distributed Computing, special issue on Scheduling and Load Balancing, December 1992.
R. Jain, K. Somalwar, J. Werth, and J. C. Browne, “Heuristics for Scheduling I/O Operations,” IEEE Trans. on Parallel and Distributed Systems, Vol 8(3), 1997.
X. Li and M. Hamdi, “λ-ADJUST Algorithm for Optical Switches with Reconfiguration Delay,” in Proc. of International Conference on Communications (ICC'03), 2003.
M. A. Marsan, A. Bianco, E. Leonardi, F. Neri and A. Nucci, “Efficient Multi-Hop Scheduling Algorithms for All Optical WDM Broadcast-and-Select Networks with Arbitrary Transceivers Tuning Latencies,” in Proc. of IEEE GLOBECOM'98, Sydney, Australia, November 1998.
M. Prais and C. C. Ribeiro, “Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment,” INFORMS Journal on Computing, Vol. 12, pp. 164-176, 2000.
F. Rendl, “On the complexity of decomposing matrices arising in satellite communication,” Operations Research Letters, Vol. 4, pp. 5-8, 1985.
C. C. Ribeiro, M. Minoux and M. C. Penna, “An Optimal Column-Generation-with-Ranking Algorithm for Very Large Scale Set Partitioning Problems in Traffic Assignment,” European Journal of Operational Research, Vol. 41, pp. 232-239, 1989.
G. N. Rouskas and M. H. Ammar, “Analysis and Optimization of Transmission Schedules for Single-hop WDM Networks,” IEEE/ACM Transaction on Networking, Vol. 3, pp. 211-221, April 1995.
G. N. Rouskas, V. Sivaraman, “Packet Scheduling in Broadcast WDM Networks with Arbitrary Transceivers Tuning Latencies,” IEEE/ACM Transactions on Networking, Vol. 5(3), pp. 359-370, June 1997.
B. Towles and W. J. Dally, “Guaranteed Scheduling for Switches with Configuration Overhead,” in Proc. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies INFOCOM'02, pp. 342-351, June 2002.
T. Weller, B. Hajek, “Scheduling Nonuniform Traffic in a Packet-switching System with Small Propagation Delay,” IEEE/ACM Transactions on Networking, Vol. 5(6), pp. 813-823, December 1997.